1. Field of the Invention
The present invention relates to methods and apparatuses for efficiently carrying out computations in finite fields of odd prime characteristic on binary hardware. The invention is particularly useful for carrying out such computations in cryptography and in error correction, but is not limited to such uses.
2. Background Information
Some Basic Aspects of Finite Fields
A finite field (also called a Galois field) is a finite algebraic structure, possessing two well-defined operations: an “addition” and a “multiplication”. A finite field with N elements exists if and only if N is the power of a prime number, i.e. N=pn for some prime p=2, 3, 5, . . . such as discussed in R. Lidl and H. Niederriter, Introduction to Finite Fields and Their Applications, Cambridge University Press, Cambridge, Revised ed., 1994. This field is unique up to an isomorphism and is normally denoted GF(pn). For a prime p, the ground field GF(p) is simply the integers under addition and multiplication modulo p. In general, if F is a field of q=pk elements (i.e. F=GF(pk)), the extension field of degree l can be defined, denoted as F[t]/(f(t)), where f(t) is a polynomial of degree l, irreducible over F. This extension field may also be referred to as GF(plk). This then gives (the unique) finite field of ql elements. In other words, this is the field of plk=pn elements. The number p is called the characteristic of the field. The well-known fact that the two fields of the same size are isomorphic does not necessarily mean that the mapping between the fields is trivial. However, constructions of such mappings are not necessary for the present invention and, in any event, are within the purview of one of ordinary skill in the art and are discussed in textbooks, such as Introduction to Finite Fields and Their Applications referred to above.
There are two predominant ways to represent a finite field. One representation is the normal basis representation well known to those of ordinary skill in the art and such as described in Introduction to Finite Fields and Their Applications referred to above. The main advantage with a normal basis is that it facilitates multiplying elements by themselves, i.e. squaring-type operations. The normal basis representation is not discussed further here. Some computational aspects associated with normal basis representations are discussed in U.S. Pat. No. 4,587,627 (Computational method and apparatus for finite field arithmetic), U.S. Pat. No. 4,567,600 (Method and apparatus for maintaining the privacy of digital messages conveyed by public transmission), and U.S. Pat. No. 5,854,759 (Method and apparatus for efficient finite field basis conversion), the entire contents of each of which are incorporated herein by reference.
Another representation is known as the polynomial basis representation. In this representation, field elements of GF(pk) may be thought of as polynomials of degree at most k−1 whose coefficients are field elements of the ground field GF(p), i.e., integers in the set (0, . . . , p−1). A typical element, γ, in the field can therefore be expressed asγ=γk−1tk−1+ . . . +γ1t+γ0,  (1)for some integers γi where 0≦γi≦p−1, and where t is a formal variable. The field element γ may also be viewed as the k-dimensional vector (γk−1, . . . , γ1, γ0), and the polynomial basis representation as referred to herein is intended to encompass this view. Another aspect of the polynomial basis representation is the choice of a polynomial h(t) of degree k and irreducible over GF(p) that is utilized in multiplication of field elements. This will be discussed in greater detail below. Because any two fields of the same size are isomorphic, it does not matter which irreducible h(t) is chosen. From system point of view, h(t) is a system parameter that is agreed upon for the particular use in mind.
As noted above, an extension field of degree l over the field F=GF(pk) can be denoted as F[t]/(f(t)) or as GF(plk). An element of the extension field can be viewed as a polynomial of degree at most l−1 whose coefficients are elements of GF(pk). In other words, an element of the extension field may be viewed as a polynomial with other polynomials as field coefficients. An element γ of the extension field can be written asγ=γl−1tl−1+ . . . +γ1t+γ0,  (2)where each γJ is a polynomial of degree at most k−1 having coefficients in the set (0, . . . , p−1). Thus, the polynomials γj can be written asγJ=γk−1,Juk−1+ . . . +γ1,ju+γ0,j  (3)where another formal variable, u, has been chosen for these polynomials to avoid confusing them with the extension-field polynomial, whose formal variable is t. This extension-field formulation using a polynomial basis representation will be used to describe the present invention.
The sum of two elements α, β in GF(pk) is defined by simply adding the corresponding polynomials (or, equivalently, vectors):α+β=(αk−1+βk−1)tk−1+ . . . +(α1+β1)t+(α0+β0),  (4)where each (integer) coefficient (αi+βi) is computed modulo p. The complexity (in terms of the number of modulo-p operations) of adding two elements by directly using the definition in equation 4 above is equal to k. For example, for the finite field GF(32) where p=3, a field element α=(2, 1) in vector notation can be written as the polynomial α=2t+1, and a field element β=(2, 2) in vector notation can be written as the polynomial β=2t+2. The sum of these field elements is (α+β)=(2+2)t+(1+2) where each coefficient is evaluated modulo 3 (mod 3). Thus, the sum reduces to (α+β)=t because 4 mod 3=1 and 3 mod 3=0. In vector notation, the sum is (1, 0).
The product of two field elements is defined by forming their product modulo h(t), where h(t) is a polynomial of degree k and irreducible (i.e., cannot be factored) over GF(p):α·β=δ2k−2t2k−2+δ2k−3t2k−3+ . . . +δ1t+δ0 mod h(t)  (5)where δi=Σjαjβi−J mod p. Here “mod h(t)” means taking the remainder when dividing by h(t), using standard polynomial division. This leaves the result with a degree strictly less that that of h(t), i.e. less than k, as desired. The complexity of multiplying two elements according to this definition is clearly on the order of k2. Alternatively, using the Karatsuba algorithm known to those of ordinary skill in the art, multiplication can (asymptotically in k) be performed with roughly k1.6 operations, but this algorithm involves more administration of the computations. The Karatsuba algorithm is, therefore, only beneficial for large values of k, for example, k>100, as noted in §4.4.3 of D. Knuth, Seminumerical Algorithms, Vol. 2 of The Art of Computer Programming, 2nd ed, Addison-Wesley, Reading, Mass., 1981.
As an example, to multiply the field elements α=(2, 1) and β=(2, 2) of finite field GF(32), a polynomial h(t) of degree k=2 and irreducible over GF(3) must be chosen, and the polynomials 2t+1 and 2t+2 are then multiplied modulo h(t). An appropriate irreducible polynomial is h(t)=t2+t+2. Then, α·β=(4t2+6t+2)mod h(t)=4(t2+t+2)+2t−6=2t (because 2 mod 3=2 and 6 mod 3=0). Thus, α·β=2t or (2, 0) in vector notation.
For an extension field (also referred to as a composite field), the formulas for addition and multiplication are the same. However, it is recognized that all coefficient-wise operations are carried out over the ground field, which may itself involve polynomial arithmetic.
Subtraction in a finite field can be done by simply noting that in the field GF(p), the negative of an element x is p−x. Thus, an element x can be replaced with p−x to obtain the negative, and then normal coefficient-wise addition may be carried out to obtain the subtraction. Division can be carried out by multiplying by the inverse as known to those skilled in the art.
Conventional Utilization of Finite Fields
The use of finite fields is central to many applications. In particular, for communication purposes, finite fields are very useful. For example, by embedding messages into a finite field, one can transmit messages so that errors introduced by the transmission medium can be corrected at the receiver end. This is the principle behind error correcting codes. In addition, finite fields can be used to achieve protection (confidentiality, integrity, origin authentication, and non-repudiation) for messages by means of encryption, message authentication, and digital signatures.
To be useful, these coding and encryption operations involving finite fields must be as efficient as possible, especially if the computations are done on a lightweight platform such as a mobile phone or other handheld device. For instance, many cryptographic methods use the following exponentiation operation
                                          exp            g                    ⁡                      (            x            )                          =                                                            g                ·                g                            ⁢                                                          ⁢              …              ⁢                                                          ⁢              g                        =                          g              x                                            (                          x              ⁢                                                          ⁢              times                        )                                              (        6        )            where g is an element in the multiplicative group of a finite field, x is an integer and “·” denotes multiplication in the finite field. The reason for using the expg(x) function is that expg(x) can be computed with only approximately (log2 x)3 field multiplications in the ground field, but no efficient (i.e. polynomial-time in log2 x) algorithm exists for the inverse transformation—finding x from expg(x). The latter is known as the discrete logarithm problem. In other words, expg(x) is a strong candidate for a so-called one-way function—a function easy to compute, but hard to invert. The discrete logarithm problem is well known to those of ordinary skill in the art and is discussed, for example, in Handbook of Applied Cryptography by A. Menezes, P. van Oorschot, and S. A. Vanstone, CRC Press, Boca Raton, Fla., 1997.
However, on a computationally weak platform, even (log2 x)3 multiplications may be computationally excessive, and for currently recommended field sizes (e.g., key size) such computations might in many situations take about 30 seconds, for example. A conventional way to improve performance is to restrict the computations to binary finite fields (fields of characteristic two). Restricting computations to binary finite fields improves performance because most available hardware is binary in nature (e.g., CPUs, etc.). Therefore, field operations can be composed of elementary binary operations, such as bitwise XORs, which are directly and efficiently supported by the hardware.
In addition, methods have been devised to improve efficiency by carrying out computations using a binary extension field whose extension degree is a composite number (non-prime), as disclosed in E. De Win, A. Bosselaers, S. Vanderberghe, P De Gersem, and J. Vandewalle, “A fast Software Implementation for Arithmetic Operations in GF(2n)”, Advances in Cryptology, Proceedings of Asiacrypt '96, LNCS 1163, Springer-Verlag, Berlin, 1996, pp. 65–76 (hereinafter “De Win et al.”). In the De Win et al. method, a standard binary hardware architecture is assumed to be able to perform operations (normal arithmetic and bit-operations) on k bit quantities (i.e., the word length is k bits). It is further noted that for an even characteristic (binary) field where p=2, forming remainders modulo 2 can be done by a simple bit operation.
When n is not a prime number, the finite field GF(2n) is viewed as a “non-trivial” extension of degree l over GF(2k), where n=lk, and l,k>1. Thus, an element in the field can be written asγ=γl−1tl−1+ . . . +γ1t+γ0,  (7)where each γi is an element of GF(2k). Adding field elements α and β in this representation can be done by carrying out the operationα+β=(αl−1+βl−1)tl−1+ . . . +(α1+β1)t+(α0+β0).  (8)Since αi, βi are elements of GF(2k), their sum, α1+β1 can be computed as the bitwise XOR between the αi and βi. Thus, if k is small enough to fit in a hardware register (typically k≦32), k additions can be performed in parallel using only one operation in hardware, and a factor of k is gained in the speed of executing the addition.
Multiplication using the De Win et al. method is carried out noting that the multiplicative group of GF(2k) (or any other finite field) is always cyclic, meaning that there is an element g in GF(2k) so that any non-zero element, αj, in the field can be written as αj=gx for some integer 0≦x<2k−1 (i.e., x is the discrete logarithm of αj, and g is known as the generator). If k is moderately large (e.g., k≦16), the generator g can be found by exhaustive search. Also, in this case (e.g., k≦16), a table, ANTILOG{x}, of gx for all x where 0≦x<2k−1 can be formed. In addition, a table for the discrete logarithms, DLOG{αj}, for all non-zero αJ in the field GF(2k) can also be formed. That is,ANTILOG{DLOG{αJ}}=αj  (9)andDLOG{ANTILOG{x}}=x  (10)for all such αj and x. The product of α and β in GF(pn) is computed in accordance with the equationα·β=δ2l−2t2l−2+δ2l−3t2l−3+ . . . +δ1t+δ0 mod f(t)  (11)where δi=Σjαjβi−j is computed as a sum of products, and all operations take place in the field GF(2k). Given that gxgy=gx+y, each term αjβi−j can be computed by three table look-ups in the above-noted pre-computed tables in accordance with the equationαJβi−J=ANTILOG{DLOG{αj}+DLOG{βi−j} mod(2k−1)}.  (12)The memory requirement is about k·2k−2 bytes, and the number of operations to perform the multiplication is on the order of l2=(n/k)2. A factor of k2 is thus gained in speed. The approach requires pre-computation of the tables and requires memory to store those tables. If k is moderate (e.g., k≦16), it is feasible to use this method using on the order of 2k pre-computation operations.
In contrast, for finite fields of odd characteristic p where p is an odd prime, the situation is more complicated than for binary finite fields because the basic operations needed for odd-characteristic finite fields are not modulo-2 operations (bit-operations) but, rather, modulo-p operations. The De Win et al. addition method as described therein, for example, is not applicable to finite fields of odd characteristic (p=3, 5, 7, . . . ), and no similar method for finite fields of odd characteristic has been reported to the knowledge of Applicants. Carrying out odd-characteristic finite-field computations in a conventional manner involves modular arithmetic, which requires long divisions. Most hardware supports modular arithmetic, but only on a word-oriented level. Thus, the above-noted optimizations for computations involving binary finite fields are not realized for computations involving odd-characteristic finite fields.
For the above noted reasons, binary finite fields have been the most widely used finite fields in error correction and cryptography. However, Applicants note that restricting such computations to binary fields can have drawbacks. For example, algorithms for inverting the expg(x) function noted above are more efficient if the field has characteristic two (a binary field) than if the field has a characteristic that is odd. Thus, the cryptographic strength of the function expg(x) may be expected to be less for binary fields than for general odd-characteristic finite fields. Indeed, it has recently been suggested that implementing cryptography using finite fields of odd characteristic and composite degree can provide enhanced cryptographic security compared to other cryptographic approaches involving finite fields, and that the gains in cryptographic security can be expected to outweigh the computational costs of such computations (see K. Rubin and A. Silverberg, “Supersingular Abelian Varieties in Cryptology”, Crypto 2002, Lecture Notes in Computer Science, Vol. 2442, ed. M. Jung, Springer-Verlag, Berlin, pp. 336–353, 2002). In addition, in the case of binary fields of composite degree where the optimizations described in the De Win et al. article referred to above are applicable, attacks on elliptic curve cryptosystems over such fields have been recently found as described in N. P. Gaudry, F. Hess, and N. P. Smart “Constructive and Destructive Facets of Weil Descent on Elliptic Curves”, Technical Report CSTR-00-016, Department of Computer Science, University of Bristol, October 2000, and in N. P. Smart, “How secure are elliptic curves over composite extension fields?”, Technical Report CSTR-00-017, Department of Computer Science, University of Bristol, November 2000. Thus, it is advisable to avoid such binary fields of composite degree for encryption. These attacks are much less effective if the finite field has odd characteristic (even if the degree is non-prime), so they are not a relevant threat in that case. However, as noted above, utilizing conventional computational methods involving odd-characteristic finite fields requires sacrificing the computational optimizations that would otherwise be gained using a binary finite field structure.